package MiddlePractice;

import org.junit.Test;

public class Demo279 {
//	279. 完全平方数
//	给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
//
//	给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
//
//	完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
	
	public int numSquares(int n) {
		
		int[] dp = new int[n+1];
		dp[0] = 0;
		dp[1] = 1;
		
		for(int i=2; i<=n; i++) {
			//开方取最大的sqrt范围
			int sqrt = (int)Math.sqrt(i);
			int minNum = i;
			//选择哪一个
			for(int k=sqrt; k>=1; k--) {
				int left = i - k*k;
				minNum = Math.min(minNum, dp[left] + 1);
			}
			dp[i] = minNum;
		}
		
		return dp[n];
    }
	
	@Test
	public void test_279() {
		System.out.println(numSquares(12));
	}
}
